# Import various libraries
# These are not important right now!
import os, sys, re

# Context Free Grammar Class
class CFG:
  # Place variables here
  CFG = {}
  crt = 0
  # Constructor
  # Place necessary variables behind self
  def __init__(self):
    print "CFG initialised"

  # Function to process a production rule
  # This is where Cem comes in
  def processrule(self, rule):
    #print rule[0]
    ruleHead = str(rule[0])
    ruleResult = rule[1]
    
    #if we have the start symbol rule[0] in the dictionary..
    if ruleHead in self.CFG:                                         
      #and if we have the end symbol rule[1] under the start symbol, first find the 'index' of that rule[1], then increase the frequency of the rule by one
      if ruleResult in [x for (x,y) in self.CFG[ruleHead]]:          
        index=[x for (x,y) in self.CFG[ruleHead]].index(ruleResult)
        self.CFG[ruleHead][index]=(ruleResult,self.CFG[ruleHead][index][1]+1)
      #if we don't have rule[1] under rule[0], create a new one with freq. 1  
      else: self.CFG[ruleHead].append((ruleResult,1))
    #if there's no rule[0] in the dictionary, create a new one as a list with it's corresponding tuple (rule[1] and freq. 1) inside it
    else: 
	self.CFG[ruleHead] = []
    	self.CFG[ruleHead].append((ruleResult,1))
    #--debug
    if(not self.crt==len(self.CFG)):
    	print len(self.CFG), rule[0]
	self.crt = len(self.CFG)
    #print '<                      >'
        

  
    
      
if __name__ == "__main__":
  # Open file and create array of lines
  # The lines now contain an unparsed tree
  f = open('wsj.02-21.training.nounary', 'r')
  trees = f.readlines()

  # Make an instance of the Context-Free-Grammar Class as defined above
  CFG = CFG()

  # For each tree in trees
  for tree in trees:
    # Start with an empty stack
    stack = []
    # Split the tree into words using space as the separation symbol
    for i in tree.split():
      # If the first symbol is a '(' then it is a non-terminal symbol so we insert the symbol
      # into the array behind the top symbol in sour stack (unless the stack is empty)
      if(i[0]=='('): 
        if(not stack==[]):
          stack[-1][1].append(i[1:])
        # Push the symbol onto the stack
        stack.append((i[1:], []))
      # If the first symbol is not a '(' then it is a terminal symbol (aka a word)
      # Then count the amount of ')' symbols on the end of the word
      # Append the word to the list on top of the stack
      else: 
        parc = list(i).count(')')
        stack[-1][1].append(i[0:-parc])
        # For each ')' pop a rule from the stack and process this rule into the CFG
        for popper in range(0, parc):
          CFG.processrule(stack.pop(-1))
          
  # You now have a Context-Free-Grammar        
  print len(CFG.CFG)
  
